package com.lagou;

public class Gold {


    /**
     * @description: 计算最大价值下挖了哪几个矿
     * @param: gold 矿数
     * @param: pnum 金矿开采所需的工人数量
     * @param: maxPeople 工人数
     */
    public static int maxValue(int[] gold,int[] pnum,int maxPeople){
        //边界
        if(gold==null|| gold.length==0) return 0;
        if(pnum==null|| pnum.length==0) return 0;
        if(gold.length!=pnum.length|| maxPeople<=0) return 0;

        //dp数组  dp[i-1]  i从1开始
        int[][] dp=new int[gold.length+1][maxPeople+1];
        for(int i=1;i<=gold.length;i++){
            for(int j=1;j<=maxPeople;j++){
                //选择的工人数超过最大工人数
                if(pnum[i-1]>j){
                    //不能选矿 等于上轮的最大价值
                    dp[i][j]=dp[i-1][j];
                }
                //选择的工人数不超过最大工人数
                else{
                    //上轮的最大价值
                    int preValue=dp[i-1][j];
                    //选择该商品后的最大价值
                    int curValue=gold[i-1]+dp[i-1][j-pnum[i-1]];
                    //两者取最大值
                    dp[i][j]=Math.max(preValue,curValue);
                }
            }
        }
        int a=dp[gold.length][maxPeople];
        //被挖矿的编号
        StringBuilder gnums = new StringBuilder(" ");
        for(int i=gold.length;i>0;i--){
            //当dp[i][j]>dp[i-1][j],这说明第i个矿是采了的
            if(dp[i][maxPeople]>dp[i-1][maxPeople]){
                gnums.insert(0, i + ",");
                //总工人数 - 已经用掉的工人数
                maxPeople=maxPeople-pnum[i-1];
            }
            if(maxPeople==0)
                break;
        }
        System.out.println("选择的金矿数："+gnums);

        return a;

    }
    public static void main(String[] args) {
        //金矿储量
        int[] gold={600,300,500,400,600};
        //人数
        int[] pnum={2,2,6,5,4};
        //人数
        int maxPeople=10;
        System.out.println("maxValue："+ maxValue(gold,pnum,maxPeople));
    }
}
